package com.likerSai;

/**
 * 最长回文字符串
 *
 * @author sun.ye
 * @since 2021-04-26 20:37
 */
public class LongestPalindrome {


    public String longestPalindrome(String s){
        char[] chars = s.toCharArray();
        int length = s.length();
        boolean[][] dictionary = new boolean[length][length];
        for (int i = 0; i < length; i++) {
            dictionary[i][i] = true;
        }

        int maxLength = 0;
        int begin = 0;
        for (int j = 1; j < length; j++) {
            for (int i = 0; i < j ; i++) {
                if (chars[i] != chars[j]){
                    dictionary[i][j] = false;
                }else {
                    if (j - i <= 2){
                        dictionary[i][j] = true;
                    }else {
                        dictionary[i][j] = dictionary[i+1][j-1];
                    }
                }

                if(dictionary[i][j] && (j - i + 1) > maxLength){
                    maxLength = j - i + 1;
                    begin = i;
                }
            }
        }

        
        return s.substring(begin,begin + maxLength);
    }
}